package review.Day_0427;

/**
 * @author zxc
 * @date 2023/04/27 21:28
 **/

import java.util.LinkedList;
import java.util.Queue;

/**
 * 题目 ：向完全二叉树中插入节点
 * 题目详述 ：
 * 完全二叉树是每一层（除最后一层外）都是完全填充（即，节点数达到最大，第 n 层有 2n-1个节点）的，并且所有的节点都尽可能地集中在左侧。
 * 设计一个用完全二叉树初始化的数据结构CBTInserter，它支持以下几种操作：
 * CBTInserter(TreeNode root)使用根节点为root的给定树初始化该数据结构；
 *
 * CBTInserter.insert(int v) 向树中插入一个新节点，节点类型为 TreeNode，值为 v 。
 * 使树保持完全二叉树的状态，并返回插入的新节点的父节点的值；
 *
 * CBTInserter.get_root() 将返回树的根节点。
 *
 * 提示：
 *
 * 最初给定的树是完全二叉树，且包含1到1000个节点。
 * 每个测试用例最多调用CBTInserter.insert 操作10000次。
 * 给定节点或插入节点的每个值都在0到5000之间。
 *
 *
 */
public class CBTInserter {
    // 即，广度优先遍历该完全二叉树（使用队列来存储）
    Queue<TreeNode> queue;
    TreeNode root;
    public CBTInserter(TreeNode root) {
        // 记录当前完全二叉树的根节点
        this.root = root;
        queue = new LinkedList<>();
        queue.add(root);
        // 广度优先遍历完全二叉树中所有节点 ：
        // while循环，直至遍历到某个TreeNode节点，不存在left节点 || right节点;
        while(queue.peek().left != null && queue.peek().right != null){
            TreeNode pollNode = queue.poll();
            queue.add(pollNode.left);
            queue.add(pollNode.right);
        }
    }

    public int insert(int v) {
        // 所要插入值v，封装为TreeNode类型的节点
        TreeNode newNode = new TreeNode(v);
        TreeNode node = queue.peek();
        // 若是队列首部节点的左子节点为空，则需要使得新插入的节点成为该节点的左子节点；
        if(node.left == null){
            node.left = newNode;
        }
        // 否则，代表队列首部节点 存在左子节点，但是右子节点为空，
        // 所以需要使得新插入的节点作为该节点的右子节点，同时将该节点移出queue队列，同时将该节点的左右子节点加入到queue队列中;
        else{
            node.right = newNode;
            queue.poll();
            queue.add(node.left);
            queue.add(node.right);
        }
        return node.val;
    }

    public TreeNode get_root() {
        // 返回完全二叉树的根节点即可;
        return root;
    }
}
